package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/system_class/section11/pojo"
)

type myShed struct {
	Head *node1

	size int
}

func newMyShed() *myShed {
	return &myShed{Head: nil, size: 0}
}

type node1 struct {
	Value *BinaryTree
	Next  *node1
}

func (receiver *myShed) ShedSize() int {
	return receiver.size
}

func (receiver *myShed) IsEmpty() bool {
	return receiver.size == 0
}
func (receiver *myShed) Offer(v *BinaryTree) {
	var n = node1{Value: v, Next: nil}
	if receiver.Head == nil {
		receiver.Head = &n

	} else {
		n.Next = receiver.Head
		receiver.Head = &n
	}

	receiver.size++
}
func (receiver *myShed) Poll() *BinaryTree {
	var v *BinaryTree = nil
	if receiver.size == 1 {
		v = receiver.Head.Value
		receiver.Head = nil
		receiver.size--

	} else {
		v = receiver.Head.Value
		receiver.Head = receiver.Head.Next
		receiver.size--
	}
	return v

}
func (receiver myShed) Peek() *BinaryTree {
	var v *BinaryTree = nil

	if receiver.Head != nil {
		v = receiver.Head.Value
	}

	return v
}

func pre(node *BinaryTree) []int {
	arr := []int{}
	if node == nil {
		fmt.Println("二叉树为空")
		return nil
	} else {
		fmt.Println("开始前序遍历")
		shed := newMyShed()
		shed.Offer(node)
		for !shed.IsEmpty() { //每次循环弹出一个值，头节点加入后弹出再往栈里压入右左节点再将自身加入数组这样先出来的是左节点所以顺序就是中左右的先序遍历
			poll := shed.Poll()
			if poll.Right != nil {
				shed.Offer(poll.Right)
			}
			if poll.Left != nil {
				shed.Offer(poll.Left)
			}

			arr = append(arr, poll.Value)
		}
	}
	return arr
}

func behind(node *BinaryTree) []int {
	arr := []int{}
	if node == nil {
		fmt.Println("二叉树为空")
		return nil
	} else {
		fmt.Println("开始后序遍历")
		shed := newMyShed()
		shed.Offer(node)
		shed2 := newMyShed()
		for !shed.IsEmpty() {
			head := shed.Poll()
			shed2.Offer(head) //每个元素从栈1出来的时候都会成为头节点

			if head.Left != nil { //栈1是左右顺序加入的所以加入栈2的时候就是右左方式所以加入栈2的最终顺序是中右左
				shed.Offer(head.Left)
			}

			if head.Right != nil {
				shed.Offer(head.Right)
			}

		}
		for !shed2.IsEmpty() {
			arr = append(arr, shed2.Poll().Value) //因为栈2里面是中右左顺序所以最终倒出来的时候就是左中右的后序遍历
		}
	}

	return arr
}

// 中序遍历通过栈来实现，口诀就是一直往左找找到一个就往栈里面压，找到底了再找其右节点
// 通过cur来确定当前找的位置，如果cur当前位nil说明需要切换节点了
// 这样子数组最先加入的肯定是最左边的节点因为他的右节点为nil所以最左边的父节点就被弹出了然后加入数组然后cur成为了这个父节点的右节点所以然后重复上述操作
// 所以数组加入元素的顺序就是左中右
func in(cur *BinaryTree) []int {
	arr := []int{}
	if cur == nil {
		fmt.Println("二叉树为空")
		return nil
	} else {
		fmt.Println("开始中序遍历")
		shed := newMyShed()
		for !shed.IsEmpty() || cur != nil {
			if cur != nil {
				shed.Offer(cur)
				cur = cur.Left
			} else {
				cur = shed.Poll()
				arr = append(arr, cur.Value)
				cur = cur.Right
			}
		}
	}

	return arr
}
func main() {
	node1 := NewBinaryTree(0) // 根节点
	node2 := NewBinaryTree(1)
	node3 := NewBinaryTree(3)
	node4 := NewBinaryTree(4)
	node5 := NewBinaryTree(5)
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5

	ints := pre(node1)
	fmt.Println(ints)

	i := behind(node1)
	fmt.Println(i)

	arr := in(node1)
	fmt.Println(arr)
}
